package shuanfa;

import java.util.Arrays;

public class MergetSort {
    public static void main(String[] args) {
        int[] arr={8,4,5,7,1,3,6,2,2};
        int[] temp=new int[arr.length];
        mergeSort(arr,0,arr.length-1,temp);
        System.out.println(Arrays.toString(arr));
    }
    //拆分，合并
    public static void mergeSort(int[] arr,int left,int right,int[] temp){
        if(left<right){
            int mid=(left+right)/2;
            //向左递归分解
            mergeSort(arr,left,mid,temp);
            //向右递归分解
            mergeSort(arr,mid+1,right,temp);
            //合并
            merge(arr,left,mid,right,temp);
        }
    }
    //合并
    public static void merge(int[] arr,int left,int mid,int right,int[] temp ){
        int i=left;//初始化i,左边有序序列的初始索引
        int j=mid+1;//初始化j,右边有序序列的初始索引
        int t=0;//指向temp数组的当前元素
        //先将左右两边数字按规则填充到临时数组中
        //直至一边填充完
        while (i<=mid&&j<=right){
            //如果左边数字大于右边数字，将右边数字填充到临时数组中
            if(arr[i]>arr[j]){
                temp[t++]=arr[j++];
            }else{
                temp[t++]=arr[i++];
            }
        }
        //然后将剩余的数字依次填充到临时数组
        while (i<=mid){
            temp[t++]=arr[i++];
        }
        while (j<=right){
            temp[t++]=arr[j++];
        }
        //最后将临时数组拷贝到原数组
        //注意，并不是每次拷贝所有
        t=0;
        int tempLeft=left;
        while (tempLeft<=right){
            arr[tempLeft++]=temp[t++];
        }
    }
}
